package com.chap13;

import java.util.Arrays;

/**
 * Created by IntelliJ IDEA.
 * User: bj910
 * Date:2023-04-12
 * Time: 5:22
 * To change this template use File | Settings | File Templates.
 */
public class MergeSort {
    private int[] orignArray;
    private int threshold;

    public MergeSort(int[] orignArray, int threshold) {
        this.orignArray = orignArray;
        this.threshold = threshold;
    }
    public int[] splitAndSort(){
        return splitAndSort(orignArray,threshold);
    }
    //拆分+排序
    public static int[] splitAndSort(int[] orignArray,int threshold){
        if (orignArray.length<=threshold){
            Arrays.sort(orignArray);
            return orignArray;
        }
        int middle = orignArray.length/2;
        int[] left = Arrays.copyOfRange(orignArray, 0, middle);
        int[] right = Arrays.copyOfRange(orignArray, middle, orignArray.length);
        left = splitAndSort(left,threshold);
        right = splitAndSort(right,threshold);
        return merge(left,right);
    }
    //合并
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length+right.length];
        int leftPointer = 0;
        int righterPointer = 0;
        int i = 0;
        //左右数组指针都没到边界
        while (leftPointer<left.length && righterPointer<right.length){
            if (left[leftPointer]<right[righterPointer]){
                result[i] = left[leftPointer];
                leftPointer++;
            } else {
                result[i] = right[righterPointer];
                righterPointer++;
            }
            i++;
        }
        while (leftPointer==left.length && righterPointer!=right.length){
            result[i] = right[righterPointer];
            righterPointer++;
            i++;
        }
        while (righterPointer==right.length && leftPointer!=left.length){
            result[i] = left[leftPointer];
            leftPointer++;
            i++;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] array = {6, 5, 3, 1, 8, 7, 2, 4};
        MergeSort mergeSort = new MergeSort(array,2);
        int[] result = mergeSort.splitAndSort();
        System.out.println(Arrays.toString(result));
    }

}
